package demo2;

import java.util.*;

public class Solution {
    //1.赎金信(哈希表)
    public boolean canConstruct(String ransomNote, String magazine) {
        //哈希表
        Map<Character, Integer> hash = new HashMap<>();
        //统计magazine中字符的个数
        for(int i = 0; i < magazine.length(); i++){
            char ch = magazine.charAt(i);
            if(!hash.containsKey(ch)){
                hash.put(ch, 1);
            }else{
                hash.put(ch, hash.get(ch) + 1);
            }
        }
        //对照
        for(int i = 0; i < ransomNote.length(); i++){
            char ch = ransomNote.charAt(i);
            if(hash.containsKey(ch)){
                hash.put(ch, hash.get(ch) - 1);
                if(hash.get(ch) < 0){
                    return false;
                }
            }else{
                return false;
            }
        }
        return true;
    }
    //2.面试题 01.01. 判定字符是否唯一(哈希表)
    public boolean isUnique(String astr) {
        //哈希表
        Set<Character> hash = new HashSet<>();
        for(int i = 0; i < astr.length(); i++){
            char ch = astr.charAt(i);
            if(!hash.contains(ch)){
                hash.add(ch);
            }else{
                return false;
            }
        }
        return true;
    }

    //3.最长回文串(哈希表)
/*    public int longestPalindrome(String s) {
        //某个单词具有偶数个，则一定可以，
        //哈希表统计个数
        Map<Character, Integer> hash = new HashMap<>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(!hash.containsKey(ch)){
                hash.put(ch, 1);
            }else{
                hash.put(ch, hash.get(ch) + 1);
            }
        }
        //奇数也可以当作偶数算进去！比如5可以当成4加进去，最后若有奇数，就加一
        int max = 0;
        int count = 0;
        boolean flag = false;
        for(char ch : hash.keySet()){
            int key = hash.get(ch);
            if(key % 2 == 0){
                count += key;
            }else{
                count += key - 1;
                flag = true;
            }
        }

        return flag ? count + 1 : count;
    }*/

    public int longestPalindrome(String s) {
        //某个单词具有偶数个，则一定可以，
        //哈希表统计个数
        Map<Character, Integer> hash = new HashMap<>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(!hash.containsKey(ch)){
                hash.put(ch, 1);
            }else{
                hash.put(ch, hash.get(ch) + 1);
            }
        }
        //奇数也可以当作偶数算进去！比如5可以当成4加进去，最后若有奇数，就加一
        int max = 0;
        int count = 0;
        boolean flag = false;
        for(Map.Entry<Character, Integer> vip: hash.entrySet()){

            int key = vip.getValue();
            if(key % 2 == 0){
                count += key;
            }else{
                count += key - 1;
                flag = true;
            }
        }
        return flag ? count + 1 : count;
    }
    //4.剑指 Offer 50. 第一个只出现一次的字符(哈希表)
    public char firstUniqChar(String s) {
        int len = s.length();
        //哈希表
        Map<Character, Integer> hash = new HashMap<>();
        for(int i = 0; i < len; i++){
            char ch = s.charAt(i);
            if(!hash.containsKey(ch)){
                hash.put(ch, 1);
            }else{
                hash.put(ch, 2);
            }
        }
        for(int i = 0; i < len; i++){
            char ch = s.charAt(i);
            if(hash.get(ch) == 1){
                return ch;
            }
        }
        return ' ';
    }
    //5.比较含退格的字符串(StringBuilder)
    public boolean backspaceCompare(String s, String t) {
        StringBuilder ss = new StringBuilder();
        StringBuilder tt = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch == '#'){
                if(ss.length() <= 0){
                    continue;
                }
                ss.deleteCharAt(ss.length() - 1);
            }else{
                ss.append(ch);
            }
        }
        for(int i = 0; i < t.length(); i++){
            char ch = t.charAt(i);
            if(ch == '#'){
                if(tt.length() <= 0){
                    continue;
                }
                tt.deleteCharAt(tt.length() - 1);
            }else{
                tt.append(ch);
            }
        }
        return ss.toString().equals(tt.toString());
    }
    //6.字符串相加(模拟竖式计算)
    public String addStrings(String num1, String num2) {
        StringBuilder ret = new StringBuilder();
        int add = 0;//进位
        int sum = 0;//当前竖列的和
        //双指针模拟竖式计算
        char ch1 = 0;
        char ch2 = 0;
        for(int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0; i--, j--){
            if(i >= 0 && j >= 0){
                ch1 = num1.charAt(i);
                ch2 = num2.charAt(j);
            }else if(i < 0){//空缺前面可以补零
                ch1 = '0';
                ch2 = num2.charAt(j);
            }else{
                ch1 = num1.charAt(i);
                ch2 = '0';
            }
            sum = ch1 + ch2 - 2*'0' + add;
            if(sum >= 10){
                add = sum / 10;
            }else{//重置add
                add = 0;
            }
            ret.append(sum % 10);
        }
        if(add != 0){
            ret.append(add);
        }
        return ret.reverse().toString();
    }
    //7.单词规律(哈希法)
    public boolean wordPattern(String pattern, String s) {
        String[] str = s.split(" ");
        //哈希法
        Map<Character, String> hash = new HashMap<>();
        //通过Map建立映射关系
        for(int i = 0, j = 0; i < pattern.length() || j < str.length; i++, j++){
            //若有一个大于长度，则说明不匹配
            if(i >= pattern.length() || j >= str.length){
                return false;
            }
            char cp = pattern.charAt(i);
            String cs = str[j];
            //若key和value都不存在，就放入
            if(!hash.containsKey(cp) && !hash.containsValue(cs)){
                hash.put(cp, cs);
            }else if(hash.containsKey(cp) && !hash.containsValue(cs)){
                //不用对比，就是错误
                return false;
            }else if(!hash.containsKey(cp) && hash.containsValue(cs)){
                //同样
                return false;
            }else{//最后都存在的时候要比较一下
                if(!hash.get(cp).equals(cs)){
                    return false;
                }
            }
        }
        return true;
    }
    //8.无重复字符的最长子串(哈希表+滑动窗口)
    public int lengthOfLongestSubstring(String s) {
        //哈希表+滑动窗口
        int left = 0;
        int right = 0;
        int sum = 0;//当前窗口大小
        int max = 0;//记录最大窗口的大小
        Set<Character> hash = new HashSet<>();
        while(left <= right && right < s.length()){
            char chLeft = s.charAt(left);
            char chRight = s.charAt(right);
            if(!hash.contains(chRight)){//不存在，放入哈希表，right往后扩大窗口
                hash.add(chRight);
                right++;
                sum++;
            }else{//若存在重复，就让left向后找到那个重复的元素
                while(chLeft != chRight){
                    hash.remove(chLeft);
                    left++;
                    chLeft = s.charAt(left);
                    sum--;
                }
                //找到了
                hash.remove(chLeft);
                left++;
                sum--;
            }
            if(sum > max){
                max = sum;
            }
        }
        return max;
    }
    //9.找出字符串中第一个匹配项的下标(记录索引法)
    public int strStr(String haystack, String needle) {
        if(haystack.length() < needle.length()){
            return -1;
        }
        //思路：遍历，并记录每一个起点下标，分别对每个起点进行遍历
        List<Integer> arr = new ArrayList<>();
        char start = needle.charAt(0);
        for(int i = 0; i < haystack.length(); i++){
            if(haystack.charAt(i) == start){
                arr.add(i);
            }
        }
        for(int i = 0; i < arr.size(); i++){
            int left = 0;
            int j = arr.get(i);
            for( ; j < haystack.length(); j++){
                if(left == needle.length() || haystack.charAt(j) != needle.charAt(left)){
                    break;
                }
                left++;
            }
            if(left == needle.length()){
                return arr.get(i);
            }
        }
        return -1;
    }
    //10.Z 字形变换(模拟)
    public String convert(String s, int numRows) {
        if(numRows == 1){
            return s;
        }
        //记录每一行的数据
        List<StringBuilder> rows = new ArrayList<>();
        //增容
        for(int i = 0; i < numRows; i++){
            rows.add(new StringBuilder());
        }
        int ans = 0;//ret的下标
        int flag = 0;//控制行打印
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ans == numRows){//说明该逆序了
                flag = -1;
                ans -= 2;
            }
            if(ans == 0){//说明该正序了
                flag = 0;
            }
            if(flag == 0){
                rows.get(ans).append(ch);
                ans++;
            }else{
                rows.get(ans).append(ch);
                ans--;
            }
        }
        //放入返回字符串
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < numRows; i++){
            ret.append(rows.get(i));
        }
        return ret.toString();
    }

}
